#include "LinkStack.h"
#include <iostream>

size_t partition(int *array, size_t start, size_t end)
{
    size_t left = start;
    size_t right = end;
    int temp = array[start];
    while (left < right)
    {
        while (array[right] > temp && left < right)
        {
            right--;
        }
        if (left < right)
        {
            array[left++] = array[right];
        }
        while (array[left] < temp && left < right)
        {
            left++;
        }
        if (left < right)
        {
            array[right--] = array[left];
        }
    }
    array[left] = temp;
    return left;
}

// 借助栈实现非递归的快速排序
// 原理：用栈记住递归区间的头和尾，借助每一层的递归记住每一个结点的位置
void FastNoRecur(int *a, size_t start, size_t end)
{
    LinkStack s; // 存放区间的栈
    s.Push((void *)start);
    s.Push((void *)end);

    while (s.IsEmpty() == false) // 栈不为空 还有区间需要排序
    {
        // 取区间
        size_t right = (size_t)*s.GetTop(); // 取出end
        s.Pop();
        size_t left = (size_t)*s.GetTop(); // 取出start
        s.Pop();

        size_t mid = partition(a, left, right); // 把区间传给分组排序
        if (mid != 0 && left < mid - 1)   // 左区间入栈
        {
            // 左区间入栈
            s.Push((void *)(left));
            s.Push((void *)(mid - 1));
        }
        if (mid + 1 < right)    // 右区间排序
        {
            // 右区间入栈
            s.Push((void *)(mid + 1));
            s.Push((void *)(right));
        }
    }
}

int main()
{
    // LinkStack s;
    // for (long i = 0; i < 20; i++)
    // {
    //     s.Push((void *)(i + 1));
    // }
    // while (s.IsEmpty() == false)
    // {
    //     std::cout << *(int *)s.GetTop() << " ";
    //     s.Pop();
    // }
    // std::cout << std::endl;

    int a[] = {4, 1, 5, 7, 9, 2, 3};
    FastNoRecur(a, 0, sizeof(a) / sizeof(a[0]) - 1);
    for (int i = 0; i < sizeof(a) / sizeof(a[0]); i++)
    {
        std::cout << a[i] << " ";
    }
    std::cout << std::endl;

    return 0;
}
